package leetcode.editor.cn;

import java.util.*;

/**
  * 题目Id：LCR 007
  * 题目：三数之和
  * 日期：2023-12-13 17:35:20
*/
//给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 
//不重复 的三元组。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：nums = [0]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 3000 
// -10⁵ <= nums[i] <= 10⁵ 
// 
//
// 
//
// 
// 注意：本题与主站 15 题相同：https://leetcode-cn.com/problems/3sum/ 
//
// Related Topics 数组 双指针 排序 👍 136 👎 0


public class OneFGaJU {
    public static void main(String[] args) {
        Solution solution = new OneFGaJU().new Solution();
        List<List<Integer>> lists = solution.threeSum(new int[]{-2,0,0,2,2});
        System.out.println(lists);

        System.out.println("Hello world");
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     *
     */
    class Solution {
        /**
         *三数之和：
         * 1，数组长度小于3
         * 2，排序，一下皆为排序后
         * 3，所有元素大于0
         * 4，遍历数组 i
         * 4.5，判断i是否重复，重复就继续下一轮
         * 5,左右指针i+1和n-1,<0 左指针向右，大于0 右指针向左
         * 6，等于0，加入
         */
    public List<List<Integer>> threeSum(int[] nums) {
        Map<List<Integer>,Object> lists = new HashMap<>();
        if(nums.length<3){
            return new ArrayList<>(lists.keySet());
        }
        Arrays.sort(nums);
        if(nums[0]>0){
            return new ArrayList<>(lists.keySet());
        }

        for (int i = 0; i < nums.length-2; i++) {
            if(i>=1&&nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1,right= nums.length-1;
            while (left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if(sum<0){
                    left++;
                }else if (sum>0){
                    right--;
                }else {
                    List<Integer> list = Arrays.asList(nums[i], nums[left], nums[right]);
                    lists.put(list,1);
                    left++;
                    right--;
                }
            }

        }

        return new ArrayList<>(lists.keySet());




    }
}
//leetcode submit region end(Prohibit modification and deletion)

} 
